#include <iostream>
#include <vector>

using namespace std;

// https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ans;
        vector<int> curCnt(26, 0);

        for (char ch : p)
        {
            curCnt[ch - 'a']++;
        }

        int left = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int curIndex = s[i] - 'a';
            curCnt[curIndex]--;
            while(curCnt[curIndex] < 0){
                curCnt[s[left++] - 'a']++;
            }
            if(i - left + 1 == p.size()){
                ans.push_back(left);
            }
        }
        return ans;
    }
};